package day03

// day03
//
// 309. 买卖股票的最佳时机含冷冻期
//
// https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-cooldown/
//
// ```go
func maxProfit(prices []int) int {
	//dp[i][j]:第i天，j状态下，获得的最大利润
	//j:0-3
	//0:买入股票状态->今天买入 or 保持之前买入
	//1:卖出股票状态->今天卖出 or 保持之前卖出
	//2:冷冻期状态->昨天卖出 or 保持之前冷冻
	dp := make([][3]int, len(prices))
	dp[0][0] = -prices[0]
	for i := 1; i < len(prices); i++ {
		dp[i][0] = max(dp[i-1][2]-prices[i], dp[i-1][0])
		dp[i][1] = max(dp[i-1][0]+prices[i], dp[i-1][1])
		dp[i][2] = max(dp[i-1][1], dp[i-1][2])
	}
	return max(dp[len(prices)-1][1], dp[len(prices)-1][2])
}

//```

// 714. 买卖股票的最佳时机含手续费
//
// https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/
//
// ```go
func maxProfit(prices []int, fee int) int {
	//dp[i][j]
	//j:0-1
	//0: 买入->今天买入 or 之前买入
	//1: 卖出->今天卖出 or 之前买出
	dp := make([][2]int, len(prices))
	dp[0][0] = -prices[0]
	for i := 1; i < len(prices); i++ {
		dp[i][0] = max(dp[i-1][1]-prices[i], dp[i-1][0])
		dp[i][1] = max(dp[i-1][0]+prices[i]-fee, dp[i-1][1])
	}
	return dp[len(prices)-1][1]
}

//```

// 300. 最长递增子序列
//
// https://leetcode.cn/problems/longest-increasing-subsequence/
//
// ```go
func lengthOfLIS(nums []int) int {
	dp := make([]int, len(nums)+1)
	for i := range dp {
		dp[i] = 1
	}
	ans := 0
	for i := 1; i < len(nums); i++ {
		for j := 0; j < i; j++ {
			if nums[i] > nums[j] {
				dp[i] = max(dp[i], dp[j]+1)
			}
		}
		ans = max(ans, dp[i])
	}
	return ans
}

//```
